Section: Partnerships and Cooperations

International Initiatives

ANR Gratel

André Raspaud launched in 2005 a fruitful cooperation with the Department of Applied Mathematics of the Sun Yat-Sen University of Kaohsiung, Taiwan. This gave rise to an international ANR project funded for three years (January 2010 - December 2013), that is managed by Arnaud Pêcher. The scientific priority theme is “Telecommunications”, a well-known key application area of graph theory. The aim is to tackle especially wireless communications problems, with the help of graph colorings and polyhedral graph theory. Currently, Sagnik Sen (PhD student of E. Sopena, A. Pêcher, A. Raspaud) benefits from a scholarship on this ANR.

INRIA Associate Team: SAMBA

• Title: Synergies for Ameliorations and Mastering of Branch-and-price Algorithms

• INRIA principal investigator: François Vanderbeck

• International Partner:

  • Institution: Pontificia Universidade Catolica do Rio de Janeiro (Brazil)

  • Laboratory: ATD-Lab

  • Researcher: Marcus Poggi, Artur Pessoa, and Eduardo Uchoa

• Duration: 2011 - 2013

• See also: https://wiki.bordeaux.inria.fr/realopt/pmwiki.php/Project/Samba

• The so-called Dantzig-Wolfe decomposition approach has not yet made its way into general purpose solvers for Mixed Integer Programming (MIP). Despite its proved efficiency, the use of the method is currently restricted to specific applications and requires ad-hoc algorithms developed by experts. Our project is to develop general purpose algorithms to make this method generic. We shall focus in particular on (i) preprocessing procedures, (ii) warm-starting, (iii) stabilization (to improve convergence), (iv) strategies for combining cut and column generation, and (v) primal heuristics. The project builds on the accumulated experience of both the Brazilian and the French teams that have done pioneering work in tackling complex applications and deriving generic solution strategies using this decomposition approach. The new algorithms shall be implemented and tested in the software platform BaPCod. (BaPCod is a generic Branch-and-Price code developed by ReAlOpt as a C++ library that is build as a layer above MIP solvers.) Hence, the collaborative research on methodological developments should lead to, as a bi-product, a Version 2 of BaPCod as a state-of-the-art Branch-and-Price-and-Cut Solver. This prototype should (i) serve as proof-of-concept code for the research planned in this project and beyond, (ii) enable us to achieve new benchmark results on key problems, (iii) provide incentive for the use of the method by non experts, (iv) leverage technology transfer to industry.

Visits of International Scientists

Short term Visitors

• Mathieu Van Vyve, CORE and LSM, Université catholique de Louvain, Belgium.

• Claudia d'Ambrosio, DEIS, Università di Bologna, Italy.

• Marcus Poggi, Departamento de Informatica, PUC-Rio, Brazil.

• Artur Pessoa, LOGIS, the Universidade Federal Fluminense, Brazil.

• Eduardo Uchoa, LOGIS, the Universidade Federal Fluminense, Brazil.

Internships

• Internship IMB–Ecole Polytechnique: André Linhares: "Dynamic Programming Algorithms for the Resource Constrained Shortest Path Problem", April - August 2011, F. Vanderbeck, R. Sadykov

• Master internship: Damien Trut: "Collecting Containers: operationnal planning", March - September 2011, F. Vanderbeck, R. Sadykov